package offer;

@FunctionalInterface
public interface FindBall {
    /**
     * You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.
     *
     * Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.
     *
     * A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
     * A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.
     * We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.
     *
     * Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.
     *
     * @param grid 一个m x n矩阵
     * @return 返回球的坠落情况
     */
    int[] findBall(int[][] grid);
}
class Test{
//    static final int[][] TEST_01 = new int[][]{{1, 1, 1, -1, -1}, {1, 1, 1, -1, -1}, {-1, -1, -1, 1, 1}, {1, 1, 1, 1, -1}, {-1, -1, -1, -1, -1}};
//    static final int[][] TEST_02 = new int[][]{{1,-1,1,1,-1,1,-1}};
    static final int[][] TEST_03 = new int[][]{{-1,1,-1,-1,-1,-1,-1,-1,1,-1,-1,-1,-1,1,1,-1,-1,-1,1,1,1,-1,-1,1,1,-1,-1,1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1,-1,1,-1,-1,-1,-1,-1,-1,-1,1,-1,-1,1,-1,1,-1,-1,1,1,-1,1,-1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,-1,1,1,1,-1,-1,-1,1,-1,1,-1,-1,1,1,-1,-1,1,-1,1,-1,1,1,1,-1,-1,-1,-1}};
    public static void main(String[] args) {
        new FindBallImpl1().findBall(TEST_03);
    }
}
class FindBallImpl1 implements FindBall {
    /**
     * 时间复杂度o(mn),空间复杂度o(m)，由于使用了递归，当球可以落到最下方时，函数栈的深度为m，即矩阵的行数
     * 考虑多源BFS
     */

    static final int TOP_LEFT_TO_BOTTOM_RIGHT = 1;
//    static final int TOP_RIGHT_TO_BOTTOM_LEFT = -1;
    // 卡住
    static final int STUCK = -1;

    private int m;
    private int n;
    private int[][] grid;

    @Override
    public int[] findBall(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = dfs(0, i, true);
        }

        return ans;
    }

    private int dfs(int row, int column, boolean isUpper){
        // 位于矩阵上方
        if(grid[row][column] == TOP_LEFT_TO_BOTTOM_RIGHT){
            //遇到一个左上-右下划线的格子
            if(isUpper){
                // 球在右上侧，考虑滚动到右侧单元格的左下部分
                if(column == n - 1){
                    // 遇到了边缘，过不了
                    return STUCK;
                } else if(grid[row][column + 1] == TOP_LEFT_TO_BOTTOM_RIGHT){
                    // 右侧也为左上斜右划线格子，可以通，dfs右侧格子的下侧
                    return dfs(row, column + 1, false);
                }else{
                    // 右侧为右上-左下划线格子，出现V形挡板, 过不了
                    return STUCK;
                }
            }else{
                // 球在左下侧，考虑到滚动到下册单元格的右部分
                if(row == m - 1){
                    // 如果当前是最后一行格子的下侧，那么可以连通，返回真
                    return column;
                }else{
                    // 滚动到一个左上-右下格子的上方，或者滚动到一个右上-左下格子上方，继续遍历下侧格子上侧
                    return dfs(row + 1, column, true);
                }
            }
        }else {
            //遇到一个右上-左下划线的格子
            if(isUpper){
                if(column == 0){
                    // 遇到边缘，无法左探
                    return STUCK;
                }else if(grid[row][column - 1] == TOP_LEFT_TO_BOTTOM_RIGHT){
                    // 遇到一个左上-右下划线的格子，构成V形挡板，无法继续搜索
                    return STUCK;
                }else{
                    // 遇到一个右上-左下划线的格子，球滚到左侧格子的右下方
                    return dfs(row, column - 1, false);
                }
            }else{
                if(row == m - 1){
                    // 如果当前是最后一行格子的下侧，则连通
                    return column;
                }else{
                    // 遍历下侧格子
                    return dfs(row + 1, column, true);
                }
            }
        }
    }
}